144. Четырехугольник

Произвольный четырехугольник задан на плоскости последовательно координатами своих вершин. Определить количество прямых углов четырехугольника.

Вход. Состоит из последовательных координат вершин четырехугольника, значения которых по модулю не превышают 100.

Выход. Вывести количество прямых углов четырехугольника.

Пример входа	Пример выхода
-1 0 -1 4 2 4 4 1	1

РЕШЕНИЕ

геометрия

Анализ алгоритма

Угол четырехугольника будет прямым, если скалярное произведение векторов, лежащих на прилегающих к нему сторонах, равно нулю. Таким образом проверяем, будет ли каждый из имеющихся четырех углов прямым.

Реализация алгоритма

Координаты i-ой вершины храним в ячейках (x[i], y[i]) (0 ≤ i ≤ 3).

int x[6], y[6];

Вычисление скалярного произведения векторов (x₁, y₁) и (x₂, y₂).

int scalar(int x1, int y1, int x2, int y2)

{

return x1 * x2 + y1 * y2;

}

Основная часть программы. Читаем координаты вершин четырехугольника.

for(res = i = 0; i < 4; i++)

scanf("%d %d",&x[i],&y[i]);

Положим четвертую точку равной нулевой, а пятую равной первой.

x[4] = x[0]; y[4] = y[0];

x[5] = x[1]; y[5] = y[1];

Вычисляем скалярное произведение векторов (x_i+1 – x_i, y_i+1 – y_i) и (x_i+2 – x_i+1, y_i+2 – y_i+1). Если оно равно нулю, то угол с координатами (x_i+1, y_i+1) прямой, увеличиваем количество прямых углов res на единицу.

for(i = 0; i < 4; i++)

if (scalar(x[i+1] - x[i], y[i+1] - y[i],

x[i+2] - x[i+1], y[i+2] - y[i+1]) == 0) res++;

Выводим количество прямых углов четырехугольника.

printf("%d\n",res);